package com.rowline.admin.module.study.collections;

import java.util.*;

/**
 * ClassName:ArrayListTest
 * Created by 245167
 * on 2017/10/30  30:51
 * description:
 */
public class ArrayListTest {

    public static final int N = 20000;

    public static List values;

    static{
        Integer vals[] = new Integer[N];
        Random r = new Random();
        for (int i = 0,currval = 0; i < N; i++) {
            vals[i] = new Integer(currval);
            currval = currval +r.nextInt(200) + 1;
        }
        values = Arrays.asList(vals);
        System.out.println(values.toString());
    }

    static long searchTimelist(List mylist){
        long start=System.currentTimeMillis();
        for(int i=0;i<N;i++){
            int index=Collections.binarySearch(mylist, values.get(i));
            if(index!=i){
                System.out.println("***错误***");
            }
        }
        return System.currentTimeMillis()-start;
    }

    /**
     * 当一个元素被加到ArrayList的最开端时，所有已经存在的元素都会后移，这就意味着数据移动和复制上的开销。
     * 相反的，将一个元素加到LinkedList的最开端只是简单的未这个元素分配一个记录，然后调整两个连接。
     * 在LinkedList的开端增加一个元素的开销是固定的，而在ArrayList的开端增加一个元素的开销是与ArrayList的大小成比例的。
     * @param mylist
     * @return
     */
    static long addTimeList(List mylist){
        long start=System.currentTimeMillis();
        Integer o = new Integer(Integer.valueOf(2));
        // 开端增加一个元素
        for(int i=0;i<N;i++) {
            mylist.add(0, o);
        }
        return System.currentTimeMillis()-start;
    }


    public static void main(String[] args) {

        System.out.println("ArrayList消耗时间：" + searchTimelist(new ArrayList(values)) + "ms");
        System.out.println("LinkedList消耗时间：" + searchTimelist(new LinkedList(values)) + "ms");

        System.out.println("********************************************");

        System.out.println("ArrayList消耗时间：" + addTimeList(new ArrayList()) + "ms");
        System.out.println("LinkedList消耗时间：" + addTimeList(new LinkedList()) + "ms");

    }


//    ArrayList可以直接通过数组下标得到元素，
//    而LinkedList则需要根据所给的下标从头部或尾部开始往下标的位置依次获得下一个元素或上一个元素。
     /*  ArrayList 的get方法源码

    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
    */

    /*  LinkedList 的get方法源码

     public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    */
}
